package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

public class _354_俄罗斯套娃信封问题 {

    public static int maxEnvelopes(int[][] envelopes) {

        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0]) {
                    return e1[0] - e2[0];
                } else {
                    return e2[1] - e1[1];
                }
            }
        });


        int len = envelopes.length;
        Stack<Integer> stack = new Stack<>();
        stack.push(envelopes[0][1]);

        for (int i = 1; i < len; i++) {

            int val = envelopes[i][1];
            if (val > stack.peek()) {

                stack.push(val);
            }else {

                int index = findIndex(stack,val);
                stack.set(index,val);
            }
        }

        return stack.size();
    }

    private static int findIndex(Stack<Integer> stack, int num) {

        int left = 0,right = stack.size() - 1;

        int mid;

        while (left < right) {

            mid = ((right - left) >> 1) + left;

             if (stack.get(mid) < num) {

                left = mid + 1;
            }else{

                 right = mid;
             }
        }

        return left;
    }

    public static void main(String[] args) {

        //
        int[][]envelopes = {{5,4},{6,4},{6,7},{2,3}};
//        int[][]envelopes = {{46,89},{50,53},{52,68},{72,45},{77,81}};

        int res = maxEnvelopes(envelopes);
        System.out.println(res);
    }
}
